package com.chapter5.string;

/**
 * 
* @ClassName: KeyIndexCount 
* @Description: 建索引计数法
* 
* 时间复杂度为<b>线性</b>级别的<b>稳定</b>排序
*  
* @author minjun
* @date 2015年3月16日 下午9:03:12 
*
 */
public class KeyIndexCount {

	public static void sort(char[] c) {
		Alphabet a=Alphabet.LOWERCASE;
		int len=a.R();
		
		int[] count=new int[len+1];
		
		int N=c.length;
		
		//计数
		for(int i=0;i<N;i++){
			count[a.toIndex(c[i])+1]++;
		}
		
		//生成索引
		for(int i=0;i<len;i++){
			count[i+1]+=count[i];
		}
		
		//将元素插入新数组的指定位置
		char[] cp=new char[N];
		
		for(int i=0;i<N;i++){
			cp[count[a.toIndex(c[i])]++]=c[i];
		}
		
		for(int i=0;i<N;i++){
			c[i]=cp[i];
		}
	}

}
